package LinkList;

/*
扁平化多级双向链表
你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。
这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。
这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。

给定链表的头节点head，将链表 扁平化 ，以便所有节点都出现在单层双链表中。
让 curr 是一个带有子列表的节点。
子列表中的节点应该出现在扁平化列表中的curr 之后 和curr.next之前 。

返回 扁平列表的 head。列表中的节点必须将其 所有 子指针设置为null。

示例 1：
输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：输入的多级列表如上图所示。
扁平化后的链表如下图：
示例 2：
输入：head = [1,2,null,3]
输出：[1,3,2]
解释：输入的多级列表如上图所示。
扁平化后的链表如下图：
示例 3：
输入：head = []
输出：[]
说明：输入中可能存在空列表。
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/linked-list/fw8v5/
 */

public class _53扁平化多级双向链表 {
    public static void main(String[] args) {

        Node n1 = new Node();
        Node n2 = new Node();
        Node n22 = new Node();
        Node n3 = new Node();
        Node n4 = new Node();

        Node head = n1;

        n1.val = 1;
        n2.val = 2;
        n22.val = 22;
        n3.val = 3;
        n4.val = 4;

        n1.next = n2;
        n2.next = n22;
        n1.child = n3;
        n22.child = n4;

        n2.prev = n1;
        n22.prev = n2;
        n3.prev = n1;
        n4.prev = n22;

        flatten(n1);

        while (head != null){
            System.out.println(head.val);
            head = head.next;
        }
    }

    static class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    };

    //递推  23/26     后续在优化下  可以实现  O(child * n)  O(1)
    public static Node flatten(Node head) {
        if (head == null) {
            return head;
        }

        Node dummyhead = new Node();
        dummyhead.next = head;
        Node end;
        int count = 0;


        while (true) {


            while (head.next != null) {
                if (head.child == null) {
                    head = head.next;
                } else {
                    count++;
                    head.child.prev = head;
                    head = head.child;
                }
            }

            if (count <= 0 && head.child == null){
                break;
            }

            end = head;

            while (true) {
                if (head.child == null) {
                    head = head.prev;
                } else {
                    count--;
                    if(head.next == null){
                        head.next = head.child;
                        head.child.prev = head;
                        head.child = null;
                        break;
                    }
                    Node next = head.next;
                    end.next = next;
                    next.prev = end;
                    head.next = head.child;
                    head.child = null;
                    head = end;
                    break;
                }
            }



        }

        return dummyhead.next;

    }


    //官解递归
    //如果学会递归大部分问题都会变得简单  一定要学会
    class Solution {
        public Node flatten(Node head) {
            dfs(head);
            return head;
        }

        public Node dfs(Node node) {
            Node cur = node;
            // 记录链表的最后一个节点
            Node last = null;

            while (cur != null) {
                Node next = cur.next;
                //  如果有子节点，那么首先处理子节点
                if (cur.child != null) {
                    Node childLast = dfs(cur.child);

                    next = cur.next;
                    //  将 node 与 child 相连
                    cur.next = cur.child;
                    cur.child.prev = cur;

                    //  如果 next 不为空，就将 last 与 next 相连
                    if (next != null) {
                        childLast.next = next;
                        next.prev = childLast;
                    }

                    // 将 child 置为空
                    cur.child = null;
                    last = childLast;
                } else {
                    last = cur;
                }
                cur = next;
            }
            return last;
        }
    }


    //递归
    public Node flatten2(Node head) {
        dfs(head);
        return head;
    }

    public Node dfs(Node node) {
        Node cur = node;
        Node last = null;
        while (cur != null){
            Node next = cur.next;
            if (cur.child != null) {

                Node childlast = dfs(cur.child);
//                next = cur.next;

                cur.next = cur.child;
                cur.child.prev = cur;

                if(next != null){
                    childlast.next = next;

                    next.prev = childlast;
                }

                cur.child = null;
                last = childlast;

            }else {
                last = cur;
            }
//            cur = cur.next;  这一步会拖慢运行速度   1ms
            cur = next;         //  0ms
        }
        return last;
    }


}
